#ifndef _contest_extended_gcd_h_
#define _contest_extended_gcd_h_

#include<stdint.h>
#include<assert.h>

namespace contest
{

/**
 * px + qy = gcd(p, q)
 * @param p: First number 
 * @param q: Second number 
 **/
uint64_t extended_gcd(uint64_t p, uint64_t q, int64_t& x, int64_t& y)
{
    int64_t x1, y1;
    uint64_t g;
    if (q > p) 
        return extended_gcd(q, p, y, x);
    if (q == 0)
    {
        x = 1;
        y = 0;
        return p;
    }
    g = extended_gcd(q, p%q, x1, y1);
    x = y1;
    y = x1 - (p/q) * y1;
    return g;
}

void test_extended_gcd()
{
    int64_t x, y;
    assert(extended_gcd(1, 1, x, y) == 1);
    assert(1*x + 1*y == 1);
    assert(extended_gcd(1, 2, x, y) == 1);
    assert(1*x + 2*y == 1);
    assert(extended_gcd(1, 3, x, y) == 1);
    assert(1*x + 3*y == 1);
    assert(extended_gcd(2, 3, x, y) == 1);
    assert(2*x + 3*y == 1);
    assert(extended_gcd(2, 4, x, y) == 2);
    assert(2*x + 4*y == 2);
    assert(extended_gcd(6, 4, x, y) == 2);
    assert(6*x + 4*y == 2);
    assert(extended_gcd(5, 10, x, y) == 5);
    assert(5*x + 10*y == 5);
    assert(extended_gcd(10,10, x, y) ==10);
    assert(10*x + 10*y == 10);
}

}
#endif
